package org.example.myleet.p839;

public class Solution {
    /**
     * 18 ms
     */
    public int numSimilarGroups(String[] strs) {
        if (strs.length == 1) {
            return 1;
        }
        UnionFind uf = new UnionFind(strs.length);
        for (int i=1; i<strs.length; i++) {
            for (int j=0; j<i; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    uf.union(i, j);
                }
            }
        }
        return uf.groups;
    }

    /**
     * 检查两个字符串是够相同，超过2个字符不相同算作不同
     */
    private boolean isSimilar(String s1, String s2) {
        int diffCount = 0;
        for (int i=0; i<s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++diffCount;
                if (diffCount > 2) {
                    return false;
                }
            }
        }
        return true;
    }

    static class UnionFind {
        int[] parent;
        //记录有多少个连通分量，每个连通分量就是相同单词的集合
        int groups;

        public UnionFind(int len) {
            parent = new int[len];
            for (int i=0; i<len; i++) {
                parent[i] = i;
            }
            groups = len;
        }

        public int find(int i) {
            int p = parent[i];
            if (p != parent[p]) {
                parent[i] = find(p);
            }
            return parent[i];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            //成功连接两个连通分量时减少一个连通分量
            parent[rootX] = rootY;
            --groups;
        }
    }
}
